// 威尔逊定理
// 测试链接 ：https://acm.hdu.edu.cn/showproblem.php?pid=2973
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16724539.html
// 相关帖子 ：https://oi-wiki.org/math/number-theory/wilson/

#include <bits/stdc++.h>

#define ll long long
const int MAXN = 1000001;
const int MX = 3000008;
int s[MAXN]; // 前缀和
int prime[MAXN];
bool visited[MX];
int t, n;

void get_prime()
{
    for(ll i = 2; i < MX; ++i)
    {
        if(!visited[i])
        {
            // 将 i 这个质数映射回 [1, n]
            if((i - 7) % 3 == 0) prime[(i - 7) / 3] = 1;
            for(ll j = i * i; j < MX; j += i) visited[j] = true;
        }
    }
}

int main()
{
    get_prime();
    for(int i = 2; i < MAXN; ++i) s[i] = s[i - 1] + prime[i];
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        printf("%d\n", s[n]);
    }

    return 0;
}